class Solution {
public:
#if 0
    int fib(int n) {


        if (n == 0)
        {
            return 0;
        }

        if (n == 1)
        {
            return 1;
        }

        return fib(n-1) + fib(n-2);
    }
#endif
#if 0
    //方法2 备忘录
    int fib(int n) 
    {
        vector<int> v_t(n+1);
        return clacFib(v_t,n);
    }

    int clacFib(vector<int> &vt,int N)
    {
        if(N == 1 || N== 0)
        {
            return N;
        }

        if (vt[N] != 0)
        {
            return vt[N];
        }

        vt[N] = clacFib(vt,N-1) + clacFib(vt,N-2);
        return vt[N];

    }
#endif

    //动态规划
    int fib(int n)
    {
        if (n == 0)
        {
            return 0;
        }
        vector<int> res(n+1);
        //正着去推
        res[0] = 0;
        res[1] = 1;
        for(int i = 2;i <= n;i++)
        {

            res[i] = res[i-1] + res[i - 2];
        }

        return res[n];
    }

};